package model.adjacence;

import jgf.Node;
import jgf.Arc;
import java.util.Vector;

/**
 * The Graph class implements a mathematical graph of an arbitrary number of nodes.<br>
 * The inside implementation is based in the Adjacende Matrix System. This system provide us material to implement
 * informed algorithms over graphs.<br>
 * This version implements an undirected graph. The values of arcs including weights or whatever can be implemented by
 * adding Attributes to the newly created arcs. You can add attributes to the nodes also using the appropriate
 * functions.
 * TODO redo the class with a Hashtable to store arcs and forget about the adjacency table... or not... could be possibly a more efficient way to store if the arcs are not too much.
 * @author Marcos Garcia Ortega
 */
public class Graph{

	protected Arc[][] net;

	protected Node[] nodes;
	private int nodeIndex = 0;

	protected int numNodes;

	protected int numArcs;

	/**
	 * Creates an empty graph, with neither nodes nor arcs.
	 */
	public Graph() {
		net = null;
		nodes = null;
		numNodes = 0;
		numArcs = 0;
		String s;
	}

	/**
	 * Creates a graph with n nodes (without attributes) ando no arcs.
	 * 
	 * @param n
	 *            The number of nodes initially on the graph
	 */
	public Graph(int n) {
		nodes = new Node[n];
		for (int i = 0; i < n; i++) {
			nodes[i] = new Node();
			nodes[i].setLabel("" + nodeIndex);//TODO remove when finished with...
			//nodes[i].setIndex(nodeIndex++);
		}
		numNodes = n;
		numArcs = 0;
		net = new Arc[numNodes][numNodes];
		for (int a = 0; a < numNodes; a++)
			for (int b = 0; b < numNodes; b++)
				net[a][b] = null;
	}


	/**
	 * Returns the number of nodes of the graph.
	 * 
	 * @return The number of nodes of the graph.
	 */
	public int numNodes() {
		return numNodes;
	}

	/**
	 * Returns the number of arcs of the graph.
	 * 
	 * @return The number of arcs of the graph.
	 */
	public int numArcs() {
		return numArcs;
	}

	/**
	 * Inserts a not collegated node without attributes.
	 */
	public void insertNode() {
		Arc[][] temp1 = new Arc[numNodes + 1][numNodes + 1]; // We create a bigger matrix of adjacence.
		for (int a = 0; a < numNodes; a++)
			// Copy the old matrix.
			for (int b = 0; b < numNodes; b++) {
				temp1[a][b] = net[a][b];
			}
		for (int a = 0; a < numNodes + 1; a++) { // Ensure that the new node is not collegated.
			temp1[a][numNodes] = null;
			temp1[numNodes][a] = null;
		}

		Node[] temp2 = new Node[numNodes + 1]; // Create a bigger array of attributes for the nodes.
		for (int a = 0; a < numNodes; a++) { // Copy the old array.
			temp2[a] = nodes[a];
		}
		nodes = temp2; // Assign the new array to the object.
		nodes[numNodes] = new Node("" + nodeIndex++);
		numNodes++; // Increment the number of nodes.
	}

	/**
	 * Removes node i from the graph and all of his associated edges. All the index nodes after the node i will be
	 * decremented in 1.
	 * 
	 * @param i
	 *            The node to remove.
	 */
	public void removeNode(int i) {
		Arc[][] temp1 = new Arc[numNodes - 1][numNodes - 1]; // We create a smaller adjacence matrix.
		for (int a = 0; a < numNodes; a++)
			// Copy the old matrix into the new one
			for (int b = 0; b < numNodes; b++) {
				if (a < i) { // Keeping in mind the gap of the removed node that must not be copied.
					if (b < i)
						temp1[a][b] = net[a][b];
					else if (b > i)
						temp1[a][b - 1] = net[a][b];
				}
				if (a > i) {
					if (b < i)
						temp1[a - 1][b] = net[a][b];
					else if (b > i)
						temp1[a - 1][b - 1] = net[a][b];
				}
			}
		net = temp1; // Assign the new matrix to the object.

		Node[] temp2 = new Node[numNodes - 1];
		for (int a = 0; a < numNodes; a++) {
			if (a < i) {
				temp2[a] = nodes[a];
			}
			if (a > i) {
				temp2[a - 1] = nodes[a];
			}
		}
		nodes = temp2;

		numNodes--; // Decrement the number of nodes.
	}

	public Node getNode(int index){
		return this.nodes[index];
	}

	/**
	 * Insert the arc into the graph collegating its nodes.
	 * 
	 * @param arc
	 *            The arc to add to the graph.
	 */
	public void insertArc(Arc arc) {
		int i = arc.getFrom().getId();
		int j = arc.getTo().getId();
		net[i][j] = arc;
		net[j][i] = arc;
		numArcs++;
	}

	/**
	 * Remove the arc that links the nodes i and j.
	 * 
	 * @param i
	 *            The index of the "from" node.
	 * @param j
	 *            The index of the "to" node.
	 */
	public void removeArc(int i, int j) {
		net[i][j] = null;
		net[j][i] = null;
		numArcs--;
	}

	/**
	 * Returns the arc that links the nodes i and j.
	 * 
	 * @param i
	 *            The index of the "from" node.
	 * @param j
	 *            The index of the "to" node.
	 * @return The arc binded by i and j.
	 */
	public Arc getArc(int i, int j) {
		return net[i][j];
	}

	/**
	 * Returns a vector containing all the arcs of the graph.
	 * 
	 * @return
	 */
	public Vector<Arc> getArcs() {
		Vector<Arc> ret = new Vector<Arc>();
		for (int i = 0; i < this.numNodes; i++)
			for (int j = i; j < this.numNodes; j++)
				if (net[i][j] != null)
					ret.add(net[i][j]);
		return ret;
	}

	public Vector<Node> getNodes() {
		Vector<Node> ret = new Vector<Node>();
		for (int i = 0; i < this.numNodes; i++)
			ret.add(nodes[i]);
		return ret;
	}

	/**
	 * Transforms the graph in a square matrix of nodes X nodes filled with the tags of the arcs and zeros where there's
	 * no arc.<br>
	 * <br>
	 * Example:<br>
	 * <br>
	 * [0][5][6][3][1]<br>
	 * [5][0][0][9][0]<br>
	 * [6][0][0][5][5]<br>
	 * [3][9][5][0][3]<br>
	 * [1][0][5][3][0]
	 * 
	 * @see java.lang.Object#toString()
	 */
	@Override
	public String toString() {
		String ret = "";
		for (int a = 0; a < numNodes; a++)
			for (int b = 0; b < numNodes; b++) {
				if (net[a][b] == null)
					ret += "[0]";
				else
					// ret += "[1]";
					ret += "[" + net[a][b] + "]";
				if (b == numNodes - 1)
					ret += "\n";
			}
		return ret;
	}

	/**
	 * Converts the graph into a square matrix and fill the cells with the value of the attribute "name" of each arc.
	 * 
	 * @param att
	 *            The name of the attribute.
	 * @return A string with the graph representated by an adjacence matrix.
	 */
	public String toString(String att) {
		String ret = "";
		for (int a = 0; a < numNodes; a++)
			for (int b = 0; b < numNodes; b++) {
				if (net[a][b] == null)
					ret += "[0]";
				else
					// ret += "[1]";
					ret += "[" + net[a][b].getAttribute(att).getValue()
							+ "]";
				if (b == numNodes - 1)
					ret += "\n";
			}
		return ret;
	}

	/**
	 * Returns A clone of the graph, bringing all new brand references for boys and girls.
	 * 
	 * @see java.lang.Object#clone()
	 */
	@Override
	public Digraph clone() {
		Digraph ret = new Digraph(this.numNodes);
		ret.numArcs = this.numArcs;
		for (int i = 0; i < numNodes; i++)
			for (int j = 0; j < numNodes; j++)
				ret.net[i][j] = this.net[i][j];
		return ret;
	}

	/**
	 * Returns the graph result as the merge of the graphs g1 and g2 (g1 U g2).
	 * 
	 * @param g1 First graph to merge.
	 * @param g2 Second graph to merge.
	 * @return g1 U g2
	 */
	public static Graph merge(Graph g1, Graph g2) {
		Graph ret = new Graph(g1.numNodes());
		for (Arc a : g1.getArcs()) {
			ret.insertArc(a);
		}
		for (Arc a : g2.getArcs()) {
			ret.insertArc(a);
		}
		return ret;
	}

}